package com.Questions.DP;


/**
 * 下降路径最小和
 */
public class leetcode931 {
    public int minFallingPathSum(int[][] matrix) {
        // dp[i][j] 表示到达ij位置最优解
        // dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1])
        int n=matrix.length;
        int[][] dp=new int[n][n];
        for(int j=0;j<n;++j){
            dp[0][j]=matrix[0][j];
        }
        for(int i=1;i<n;++i){
            for(int j=0;j<n;++j){
                int left;
                int right;
                int mid;
                if(j==0){
                    left=20000;
                }else{
                    left=dp[i-1][j-1];
                }
                if(j==n-1){
                    right=20000;
                }else{
                    right=dp[i-1][j+1];
                }
                mid=dp[i-1][j];
                dp[i][j]=Math.min(Math.min(left,right),mid)+matrix[i][j];
            }
        }
        int Min=20000;
        for(int j=0;j<n;++j){
            Min=Math.min(Min,dp[n-1][j]);
        }
        return Min;
    }
}
